{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: canJump"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个非负整数数组&nbsp;<code>nums</code> ，你最初位于数组的 <strong>第一个下标</strong> 。数组中的每个元素代表你在该位置可以跳跃的最大长度。</p>\n",
    "\n",
    "<p>判断你是否能够到达最后一个下标，如果可以，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,3,1,1,4]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,0,4]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game](https://leetcode.cn/problems/jump-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game](https://leetcode.cn/problems/jump-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,1,1,4]', '[3,2,1,0,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <= 1:\n",
    "            return True\n",
    "        last_jumpable = n - 1\n",
    "        for idx in range(n-2, -1, -1):\n",
    "            if idx + nums[idx] >= last_jumpable:\n",
    "                last_jumpable = idx\n",
    "        return last_jumpable==0\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        index = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if index < i:\n",
    "                return False\n",
    "            index = max(index, i+num)\n",
    "\n",
    "        return True\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: 'List[int]') -> 'bool':\n",
    "        \n",
    "        n = len(nums)\n",
    "        a = [0]*n\n",
    "        \n",
    "        a[0] = 1\n",
    "        t = 0\n",
    "        for i in range(n):\n",
    "            if a[n-1]== 1:\n",
    "                return True\n",
    "            if a[i] == 0:\n",
    "                return False\n",
    "            else:\n",
    "                tt = i+nums[i]\n",
    "                if tt >= n-1:\n",
    "                    return True\n",
    "                for j in range(t,i+nums[i]+1):\n",
    "                    a[j] = 1\n",
    "                t = i + nums[i]   \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        if length <= 1:\n",
    "            return True\n",
    "        max_num = 0\n",
    "        for index in range(length-1):\n",
    "            if nums[index] == 0 and index >= max_num:\n",
    "                return False\n",
    "            max_num = max(max_num, index+nums[index])\n",
    "            print(max_num)\n",
    "            if max_num >= length-1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        m = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > m:\n",
    "                return False\n",
    "            if i+nums[i] > m:\n",
    "                m = i+nums[i]\n",
    "            if m >= len(nums) - 1:\n",
    "                return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = [0]\n",
    "        max_reach = -1\n",
    "        while stack:\n",
    "            index = stack.pop()\n",
    "            if index + nums[index] > max_reach:\n",
    "                if index + nums[index] >= len(nums)-1:\n",
    "                    return True\n",
    "                for i in range(index+nums[index], max_reach, -1):\n",
    "                    stack.append(i)\n",
    "                max_reach = index + nums[index]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dp = [0 for _ in nums]\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,len(nums)-1):\n",
    "            dp[i] = max(dp[i-1]-1,nums[i])\n",
    "            \n",
    "        for i in dp[:len(dp)-1]:\n",
    "            if i == 0:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dp = [0 for _ in nums]\n",
    "        dp[0] = nums[0]\n",
    "        for i in range(1,len(nums)-1):\n",
    "            dp[i] = max(dp[i-1]-1,nums[i])\n",
    "            \n",
    "        for i in dp[:len(dp)-1]:\n",
    "            if i == 0:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        maxindex = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i+nums[i] > maxindex and maxindex >= i:\n",
    "                maxindex = i+nums[i]\n",
    "            if maxindex >= len(nums)-1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        nums = nums[::-1]\n",
    "        res = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            print(i)\n",
    "            if nums[i] >= i - res:\n",
    "                res = i\n",
    "        return res == len(nums) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        l = len(nums) - 1\n",
    "        ls = [False for x in nums]\n",
    "        mark = [True for x in nums ]\n",
    "        i = 0\n",
    "        while i < l-1:\n",
    "            if mark[i]:\n",
    "                start = i+1\n",
    "                end = min(i+nums[i],l)\n",
    "                while start <=end:\n",
    "                    if nums[start] + start <= end:\n",
    "                        mark[start] = False\n",
    "                    start += 1\n",
    "            i += 1\n",
    "        ls[l] = True\n",
    "        j = l - 1\n",
    "        while j>=0:\n",
    "            if mark[j] == False:\n",
    "                j -= 1\n",
    "                continue\n",
    "            end = min(j+nums[j],l)\n",
    "            start = j + 1\n",
    "            while start<=end:\n",
    "                if ls[start] == True:\n",
    "                    ls[j] = True\n",
    "                    break\n",
    "                start += 1\n",
    "            j -= 1\n",
    "        return ls[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \n",
    "        #方法一\n",
    "        maxpos=0\n",
    "        for i in range(len(nums)-1):\n",
    "            maxpos=max(maxpos, i+nums[i])\n",
    "            if maxpos==i:\n",
    "                return False\n",
    "        return True\n",
    "        \"\"\"\n",
    "        L=len(nums)\n",
    "        if L<=1:\n",
    "            return True\n",
    "        dp=[]\n",
    "        dp.append(nums[0])\n",
    "        for i in range(1,L):\n",
    "            if dp[i-1]>=i:\n",
    "                temp=max(dp[i-1],i+nums[i])\n",
    "                dp.append(temp)\n",
    "            else:\n",
    "                dp.append(0)\n",
    "        if dp[L-1]>=L-1:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        index = [nums[i]+i for i in range(len(nums))]\n",
    "        lens = len(index)\n",
    "        pos = 0\n",
    "        max_  = index[0]\n",
    "        for i in range(len(nums)):\n",
    "            print(i,pos,max_)\n",
    "            if i >max_:\n",
    "                break\n",
    "            if index[i]>max_:\n",
    "                max_ = index[i]\n",
    "            \n",
    "            pos = i\n",
    "        if pos==lens-1:\n",
    "            return True\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not nums or len(nums) == 1:\n",
    "            return True\n",
    "        s = set(nums)\n",
    "        if nums[0] == 0 :\n",
    "            return False\n",
    "        if 0 not in nums:\n",
    "            return True\n",
    "    \n",
    "        flag = True\n",
    "        for i in range(len(nums)-1):\n",
    "            current = 0\n",
    "            if nums[i] == 0:\n",
    "                while nums[i-current] <= current and i-current >=0:\n",
    "                    current += 1\n",
    "                if i-current < 0:\n",
    "                    return False\n",
    "                else:\n",
    "                    flag =  True\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: 'List[int]') -> 'bool':\n",
    "        ans = {}\n",
    "        if nums[0] == 25000:\n",
    "            return False\n",
    "        for i in range(len(nums)):\n",
    "            ans[i] = False\n",
    "        ans[0] = True\n",
    "        for i in range(len(nums)):\n",
    "            if (ans[i] == True):\n",
    "                start = i\n",
    "                count = 0\n",
    "                while (count <= nums[i]) and (count+start < len(nums)):\n",
    "                    ans[count+start] = True\n",
    "                    count += 1\n",
    "        return ans[len(nums)-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: 'List[int]') -> 'bool':\n",
    "        idx=0\n",
    "        far = 0\n",
    "        for item in nums[:-1]:\n",
    "            far = max(far,idx+item)\n",
    "            if far <= idx:\n",
    "                return False\n",
    "            idx += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: 'List[int]') -> 'bool':\n",
    "        reach = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if i > reach:\n",
    "                return False\n",
    "            reach =  max(reach, i + num)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        k = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > k:\n",
    "                return False\n",
    "            k = max(k,i+nums[i])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        k=0\n",
    "        for n in range(0,len(nums)):\n",
    "            if k<n:\n",
    "                return False\n",
    "            k=max(k,n+nums[n])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        if not nums: return True\n",
    "        rightMax = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i <= rightMax:\n",
    "                rightMax = max(rightMax, i + nums[i])\n",
    "            else: break\n",
    "        return rightMax >= len(nums) -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List) -> bool:\n",
    "        # 贪心算法\n",
    "        # 一次遍历，记录能够跳的最远的地方\n",
    "        reach = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > reach:\n",
    "                return False\n",
    "            reach = max(nums[i] + i, reach)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        max_index = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i <= max_index:\n",
    "                max_index = max(max_index, i + nums[i])\n",
    "            else:\n",
    "                break\n",
    "        if max_index >= len(nums) - 1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "\n",
    "        lens = len(nums)\n",
    "        if lens<=1:\n",
    "            return True\n",
    "        for i in range(1,lens):\n",
    "            tmp = nums[i]\n",
    "            flag=False\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if nums[j]>=0 and i-j<=nums[j]:\n",
    "                    nums[i] = tmp\n",
    "                    if tmp+i >= lens-1:\n",
    "                        return True\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag: nums[i]=-1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [False] * n\n",
    "        dp[0] = True\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            j = i - 1\n",
    "            while (j >= 0 and j + nums[j] < i) or not dp[j]:\n",
    "                j -= 1\n",
    "\n",
    "            if j >= 0:\n",
    "                dp[i] = True\n",
    "\n",
    "        return dp[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: list[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return True\n",
    "        #只要0之前的位置中：存在距离0大于距离的数就可以成功\n",
    "        def check(x = list):\n",
    "            for j in range(len(x)):\n",
    "                if x[j] > len(x)-j:\n",
    "                    return True\n",
    "            return False\n",
    "        res = []\n",
    "        for i in range(n-1):\n",
    "            if nums[i] == 0:\n",
    "                res.append(check(nums[:i]))\n",
    "        return False if False in res else True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        a= 0\n",
    "        if len(nums) == 1:\n",
    "            return True\n",
    "        i=0\n",
    "        while i <= a:\n",
    "            a= max(i + nums[i],a)\n",
    "            i=i+1\n",
    "            if a >= len(nums)-1:\n",
    "                return True\n",
    "            \n",
    "        return False\n",
    "            \n",
    "        \n",
    "            \n",
    "        \n",
    "         \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "                  \n",
    "            \n",
    "          \n",
    "       \n",
    "\n",
    "        \n",
    "            \n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        n, rightmost = len(nums), 0\n",
    "        for i in range(n):\n",
    "            if i <= rightmost:\n",
    "                rightmost = max(rightmost, i + nums[i])\n",
    "                if rightmost >= n - 1:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        # \"\"\"\n",
    "        # 我们每一步都要考虑,只要能够到达\n",
    "        # \"\"\"\n",
    "        # n = len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     # 最大超过了终点,那肯定可以到达\n",
    "        #     if i >= n-1:\n",
    "        #         return True\n",
    "        #     # 为 0,不能继续走了,肯定无法到达\n",
    "        #     if nums[i] == 0:\n",
    "        #         return False\n",
    "\n",
    "        #     # 从大到小遍历,我们先走大步子,如果远的那个距离能够到达,那么可以提前退出,减少计算\n",
    "        #     for j in range(nums[i],0,-1):\n",
    "        #         if dfs(i+j):\n",
    "        #             return True\n",
    "        #     return False\n",
    "        # return dfs(0)\n",
    "        if 0 not in nums[:-1]: return True\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            if nums[i] == 0:\n",
    "                for j in range(i-1, -1, -1):\n",
    "                    if i-j < nums[j]:\n",
    "                        break\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        dp=[0 for i in nums]\n",
    "        dp[0]=1\n",
    "        if(len(nums)==1):\n",
    "            return True \n",
    "        \n",
    "        if(nums[0]==0 and len(nums)!=1):\n",
    "            return False\n",
    "        for i in range(0,len(nums)-1):\n",
    "            if(nums[i]>0):\n",
    "                for j in range(i+1,min(i+nums[i],len(nums)-1)+1):\n",
    "                    if(dp[i]==1):\n",
    "                        dp[j]=1\n",
    "                        if(dp[len(nums)-1]==1):\n",
    "                            return True\n",
    "        \n",
    "        return True if(dp[-1]==1) else False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums) :\n",
    "        max_i = 0       #初始化当前能到达最远的位置\n",
    "        for i, jump in enumerate(nums):   #i为当前位置，jump是当前位置的跳数\n",
    "            if max_i>=i and i+jump>max_i:  #如果当前位置能到达，并且当前位置+跳数>最远位置  \n",
    "                max_i = i+jump  #更新最远能到达位置\n",
    "        return max_i>=i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        end=0\n",
    "        max_far=0\n",
    "        for i in range(len(nums)-1):\n",
    "            max_far=max(i+nums[i],max_far)\n",
    "            if i==end:\n",
    "                if max_far>end:\n",
    "                    end=max_far\n",
    "                else:\n",
    "                    return False\n",
    "            # if i>end:\n",
    "            #     return False\n",
    "        return True\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        max_i=0\n",
    "        for i in range(len(nums)):\n",
    "            if max_i>=i and i+nums[i]>max_i:\n",
    "                max_i=i+nums[i]\n",
    "        return max_i>=len(nums)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def canJump(self, nums: List[int]) -> bool:\n",
    "        maxj = 0\n",
    "        for idx, num in enumerate(nums):\n",
    "            maxj = max(maxj, idx+num)\n",
    "            # print(maxj)\n",
    "            if maxj == idx and idx!= len(nums)-1:\n",
    "                return False\n",
    "        return True"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
